package airthmetic.exercise.heap;

import java.util.PriorityQueue;

public class 面试题17_14_最小K个数 {

    public static int[] smallestK(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0){
            return new int[]{};
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((v1, v2)->{
            return v2-v1;
        });

        for(int i=0; i<arr.length; i++){
            if(i<k){
                queue.offer(arr[i]);
            }else{
                int temp = queue.peek();
                if(temp > arr[i]){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }

        int[] res = new int[k];
        int index = 0;
        while(!queue.isEmpty()){
            res[index++] = queue.poll();
        }
        return res;
    }
    public static void main(String[] args) {
        int [] arr = new int[]{1,3,5,7,2,4,6,8};
        int k = 1;

        for (int i : smallestK(arr, k)) {
            System.out.println(i);
        }

    }
}
